Computer viruses and worms are major threats to corporate and home computer networks. Viruses and worms may cause exposure of sensitive information, congestion of computer networks, hardware and software malfunction, and other problems. Many viruses and worms attempt to replicate themselves on as many network devices as possible. To replicate itself, a virus or worm on an infected network device may cause the network device to attempt to create network connections to other network devices. If the network device successfully creates a network connection to another network device, the virus or worm may use the network connection to transmit a copy of itself to the other network device or to cause the other network device to execute malicious code.
In general, an infected network device is not preprogrammed with network addresses of network devices within the network (e.g., an enterprise network) that are online and able to accept connections with the infected network device. Consequently, the infected network device typically performs a portscan of network addresses to find vulnerable systems by attempting to establish network connections over a series of network addresses. For example, the infected network device may send an invitation to create a network connection (e.g., a Transport Control Protocol SYN message) to each Internet Protocol address in a local subnet (e.g., 68.122.053.xxx). Because the infected network device is sending invitations to network devices that may not exist or may not accept network connections, many of the invitations sent by the infected network device are rejected or simply fail. An infected network device that sends many invitations to create network connections without many of these invitations being accepted is sometimes referred to as a “suspicious network device.”
A network security device may use a threshold random walk algorithm to identify suspicious network devices. A network security device using the threshold random walk algorithm maintains a counter for each network device that has sent an invitation through the network security device. The network security device increments the counter for a network device whenever an invitation from the network device is accepted and decrements the counter for the network device whenever an invitation from the network device is rejected. If the counter for a network device falls below a minimum threshold, this indicates that the network device is sending many invitations to other network devices without many of those network devices accepting the invitations. Hence, the network security device may suspect that the network device has been infected by a virus or other threat. The network security device may then quarantine the suspected infected network device.